package lk;

import java.util.Deque;
import java.util.LinkedList;

public class D231001 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // 二叉树中的最长交错路径
    // 1. 枚举每一个节点 作为起始节点 的最长路径和
    // 超时
    // 时间：O(n^2)
    // 空间：O(n)
    public int longestZigZag(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int res = 0;

        // 当前节点为起点，最长的交错路径
        // 左右两条路
        res = Math.max(res, func(root.left, 0, -1));
        res = Math.max(res, func(root.right, 0, 1));

        // 递归遍历其他节点
        res = Math.max(res, longestZigZag(root.left));
        res = Math.max(res, longestZigZag(root.right));
        return res;
    }
    // count 表示路径长度, x 表示方向
    private int func(TreeNode node, int count, int x) {
        if (node == null) {
            return count;
        }
        if (x == 1){
            count = func(node.left, count + 1, -x);
        } else {
            count = func(node.right, count + 1, -x);
        }
        return count;
    }


    // 2. 深度优先搜索，1 的优化版本
    // 递归根结点的左右方向
    // 如果根结点向右，那么下一个节点就要向左，否则重新计数
    // 时间：O(n)
    // 空间：O(n)
    int maxAns;
    public int longestZigZag2 (TreeNode root) {
        if (root == null) {
            return 0;
        }
        maxAns = 0;

        // 从根结点开始，向左和向右两条路
        // false 表示向左
        // true 表示向右
        dfs(root, false, 0);
        dfs(root, true, 0);
        return maxAns;
    }
    public void dfs(TreeNode o, boolean dir, int len) {
        // 每次都更新最长交错路径
        maxAns = Math.max(maxAns, len);

        // !dir 为真，说明 dir 是 false，向左走
        if (!dir) {
            if (o.left != null) {
                // 左边可以走，len + 1
                dfs(o.left, true, len + 1);
            }
            if (o.right != null) {
                // 右边也可以走，但是向右走要重新计数
                dfs(o.right, false, 1);
            }
        } else {
            // 同理
            if (o.right != null) {
                dfs(o.right, false, len + 1);
            }
            if (o.left != null) {
                dfs(o.left, true, 1);
            }
        }
    }


    // 二叉树的最近公共祖先

    // 1. 递归
    // 递归左右子树
    // 时间：O(N)
    // 空间：O(N)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        //当前结点为 p 或 q 返回
        if (root == p || root == q) {
            return root;    // 返回当前节点
        }

        // 寻找当前节点的左右子树
        TreeNode left = lowestCommonAncestor(root.left, p , q);
        TreeNode right = lowestCommonAncestor(root.right, p , q);

        // 提示 p 和 q 均存在于给定的二叉树中。

        // 左右子树都找到了 p 或 q，说明当前节点是公共祖先
        // 如果只有一个子树中找到了，那么公共祖先就在这个子树中
        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else if (right != null) {
            return right;
        }
        return null;
    }



    // 2. 使用栈
    // 从根结点开始寻找 p 和 q 节点，并将寻找的路径节点存储到两个栈中
    // 然后比较两个栈的大小，将 size 大的栈，出栈一些元素，直到两个栈 size 一致
    // 然后比较栈顶元素，如果栈顶元素相同，这个元素就是最近公共祖先，否则同时出栈，继续比较，直到栈空(根结点)
    // 时间：O(N)
    // 空间：O(N)
    public TreeNode lowestCommonAncestor2 (TreeNode root, TreeNode p, TreeNode q) {
        Deque<TreeNode> stack1 = new LinkedList<>();
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(root, p, stack1);
        getPath(root, q, stack2);
        int size1 = stack1.size();
        int size2 = stack2.size();

        // 把栈中结点多的 弹出，保证两个栈结点一样多
        if (size1 > size2) {
            for (int i = 0; i < size1 - size2; i++) {
                stack1.pop();
            }
        } else if (size1 < size2) {
            for (int i = 0; i < size2 - size1; i++) {
                stack2.pop();
            }
        }

        // 然后都两个栈各弹出结点 比较
        while (!stack1.isEmpty()) {
            if (stack1.peek() == stack2.peek()) {
                return stack1.peek();
            }
            stack1.pop();
            stack2.pop();
        }

        return null;
    }

    // 找到 根结点 到 node 结点路径上所有的结点，放入栈中
    public boolean getPath(TreeNode root, TreeNode node, Deque<TreeNode> stack) {
        if (root == null ||node == null) {
            return false;
        }
        // 先放入栈中
        stack.push(root);

        // 找到了 返回
        if (root == node) {
            return true;
        }

        // 继续找左右两边
        boolean left = getPath(root.left, node, stack);
        if (left == true) {
            return true;
        }
        boolean right = getPath(root.right, node, stack);
        if (right == true) {
            return true;
        }

        // 两边都没找到，说明改结点不是路径上的结点
        // 弹出改结点
        stack.pop();
        return false;
    }
}
